package com.leetcode.algorithm.y22.m08.w1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1403. 非递增顺序的最小子序列
 * 
 * https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/
 * 
 * @author jie.deng
 *
 */
class Question1403Solution01 {

	public List<Integer> minSubsequence(int[] nums) {
		Arrays.sort(nums);
		int len = nums.length;
		int left = 0;
		int right = len - 1;
		while (left < right) {
			int tmp = nums[left];
			nums[left] = nums[right];
			nums[right] = tmp;
			left++;
			right--;
		}

		int[] prefixSum = new int[len];
		prefixSum[0] = nums[0];
		for (int i = 1; i < prefixSum.length; i++) {
			prefixSum[i] = prefixSum[i - 1] + nums[i];
		}

		left = 0;
		right = len - 1;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (prefixSum[mid] * 2 <= prefixSum[len - 1]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		List<Integer> list = new ArrayList<>();
		for (int i = 0; i <= right; i++) {
			list.add(nums[i]);
		}
		return list;
	}

}